# 六六大顺
import sys

sys.set_int_max_str_digits(10000)


def sum_square_bf(n):
    """暴力法"""
    arr = [0] * n
    arr[0] = 6
    for i in range(1, n):
        arr[i] = arr[i - 1] * 10 + 6
    res = 0
    for i in range(n):
        res += arr[i] ** 2
    return res


def sum_square(n):
    """我的方法, 模拟乘法运算 通过率= 3/10 """
    res = 0
    base = 0
    for i in range(1, n + 1):
        base += 36
        res += base
        temp = base
        for j in range(1, i):
            temp *= 10
            res += temp
        base *= 10
    return res


def sum_square_opt(n):
    """注意观察构造方法 ，观察 11= 1 1111= 121 111111= 12321 11111111=1234321
    对第i（从0开始）位，如果i<2,没有其他项，和为(i+1)*(n-i)，2<=i<n-1,有n//2项等差数列，
    i为偶数形式为1，3，...,i为奇数时为2，4，... ,i为偶数项和为n**2，i为奇数，偶数项和为n(n+1),则和的表达式为(i//2)*(i//2+i%2)，
    除此之外还有n-i项i+1 ,则和为(i//2)*(i//2+i%2)+(i+1)*(n-i)，i>=n-1,时，只有等差数列，但等差数列项数要倒过来，为f=2n-i，
    知道了第i项的和之后还要乘36，因为构造是61...1形式，考虑循环怎么写，从个位一边计算一边加最后乘36行不行？
    不行，因为累加之后数会很大，既然不能加，只能考虑字符串，那么字符串怎么构造？先求出1的和的字符串再转化为整数，再乘36？
    很显然也不现实，最后整数太大，所以只能每一位计算出来都乘36，
    但这里要注意进位问题，然后我们只需要一个s字符串和一个x（进位到下一位的数），然后循环计算s即可，最后要记得把t反过来
    总结：突破口：找1...1平方的规律以及求和规律，计算出每一位的值
    难点：复杂度优化（这数据真的很狗，我远远低估了这个数据量的庞大，本人思路中说到的会超时的方法都是我做题时尝试过的）
    数据量太大时需要考虑字符串+进位代替加法"""
    t = ''
    x = 0
    for i in range(2 * n - 1):
        if i < 2:  # 前两项
            k = (i + 1) * (n - i)
        elif 2 <= i < n - 1:  # 既有重复项又有等差数列
            k = (i // 2) * (i // 2 + i % 2) + (i + 1) * (n - i)
        else:  # 只有等差数列
            f = 2 * n - i
            k = (f // 2) * (f // 2 + f % 2)
        a = k * 36  # 乘36准备进位
        t += str((x + a) % 10)
        x = (x + a) // 10  # 下一位进位，由于之后都会取模，所以不管多少都直接进
    t += str(x)  # 最后一位
    return t[::-1]  # 要反过来


if __name__ == '__main__':
    # print(sum_square_bf(10000))
    print(sum_square_opt(10000))
